package com.gitee.feizns.explore.data_structure.linked_list.singly.reverse;

/**
 * 反转链表
 * 反转一个单链表。
 * @author feizns
 * @since 2019/9/30
 */
public class Reverse {

    public static void main(String[] args) {
        reverse(create()).print();
    }

    public static ListNode reverseList(ListNode head) {
        if ( head != null && head.next != null ) {
            ListNode curtHead = head;
            ListNode tail = head;
            ListNode curt = head.next;
            while ( curt != null ) {
                ListNode next = curt.next;
                curt.next = curtHead;
                tail.next = next;

                curtHead = curt;
                curt = next;
            }
            return curtHead;
        }
        return head;
    }

    public static ListNode reverseList2(ListNode head) {
        ListNode prev = head;
        ListNode curt = head.next;
        head.next = null;
        while ( curt != null ) {
            ListNode next = curt.next;
            curt.next = prev;
            prev = curt;
            curt = next;
        }
        return prev;
    }

    public static ListNode reverse(ListNode head) {
        return head != null ? reverse(null, head) : null;
    }

    private static ListNode reverse(ListNode prev, ListNode curt) {
        if ( curt == null )
            return prev;
        ListNode next = curt.next;
        curt.next = prev;
        return reverse(curt, next);
    }

    public static ListNode create() {
        ListNode ret = new ListNode(0);
        ret.next = new ListNode(1);
        ret.next.next = new ListNode(2);
        ret.next.next.next = new ListNode(3);
        return ret;
    }

}
